Modeling and Solving Code Generation for Real

Christian Schulte

10 septembre 2015 à 10H30

Abstract:

This talk shows how to improve code generation in compilers by using constraint programming (CP) as a method for solving combinatorial optimization problems. It presents how instruction selection (selecting processor instructions for programs), register allocation (assigning program variables to processor registers), and instruction scheduling (reordering processor instructions to increase throughput) can be modeled and solved using CP. The talk covers instruction selection, the integration of register allocation and instruction scheduling, and future plans.

The talk presents a combinatorial model that integrates global register allocation with instruction scheduling. The model covers advanced aspects such as ultimate coalescing, spill code optimization, register packing, and multiple register banks.

The talk will sketch a graph-based universal program representation that unifies data and control flow for both programs and processor instructions. The representation is the essential prerequisite for a CP model for instruction selection. The model is demonstrated to be expressive in that it supports many processor features that are out of reach of state-of-the-art approaches, such as advanced branching instructions, multiple register banks, and SIMD instructions.

The models are significant as they address the same aspects as traditional code generation algorithms, yet are based on simple models and can robustly generate optimal code.

Joint work with Mats Carlsson, Roberto Castañeda Lozano, Frej Drejhammar, and Gabriel Hjort Blindell.